/*
  Copyright 2006 by Sean Luke
  Licensed under the Academic Free License version 3.0
  See the file "LICENSE" for more information
*/


package ec.app.deferEvalCoevolve1;
import java.util.Arrays;
import java.util.SortedSet;

import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader.Array;

import ec.*;
import ec.util.*;
import ec.vector.DoubleVectorIndividual;
import ec.select.SelectDefaults;
import ec.steadystate.*;

/* 
 * DeferEval_TournamentSelection_simple.java
 * 
 * Created: Mon Aug 30 19:27:15 1999
 * By: Sean Luke
 */

/**
 * Does a simple tournament selection, limited to the subpopulation it's
 * working in at the time.
 *
 * <p>Tournament selection works like this: first, <i>size</i> individuals
 * are chosen at random from the population.  Then of those individuals,
 * the one with the best fitness is selected.  
 * 
 * <p><i>size</i> can also be a floating-point value between 1.0 and 2.0,
 * exclusive of them. In this situation, two individuals are chosen at random, and
 * the better one is selected with a probability of <i>size/2</i> 
 *
 * <p>Common sizes for <i>size</i> include: 2, popular in Genetic Algorithms
 * circles, and 7, popularized in Genetic Programming by John Koza.
 * If the size is 1, then individuals are picked entirely at random.
 *
 * <p>Tournament selection is so simple that it doesn't need to maintain
 * a cache of any form, so many of the SelectionMethod methods just
 * don't do anything at all.
 *

 <p><b>Typical Number of Individuals Produced Per <tt>produce(...)</tt> call</b><br>
 Always 1.

 <p><b>Parameters</b><br>
 <table>
 <tr><td valign=top><i>base.</i><tt>size</tt><br>
 <font size=-1>int &gt;= 1 <b>or</b> 1.0 &lt; float &lt; 2.0</font></td>
 <td valign=top>(the tournament size)</td></tr>

 <tr><td valign=top><i>base.</i><tt>pick-worst</tt><br>
 <font size=-1> bool = <tt>true</tt> or <tt>false</tt> (default)</font></td>
 <td valign=top>(should we pick the <i>worst</i> individual in the tournament instead of the <i>best</i>?)</td></tr>

 </table>

 <p><b>Default Base</b><br>
 select.tournament

 *
 * @author Sean Luke
 * @version 1.0 
 */

public class DeferEval_TournamentSelection_simple extends SelectionMethod implements SteadyStateBSourceForm
    {
    /** default base */
    public static final String P_TOURNAMENT = "tournament";

    public static final String P_PICKWORST = "pick-worst";

    /** size parameter */
    public static final String P_SIZE = "size";

    /* Default size */
    public static final int DEFAULT_SIZE = 7;

    /** number of partner-groups to use in evaluation */
	private static final String P_COMP_SIZE = "comp_size";
	
	public int comp_size = DEFAULT_SIZE;

    /** Size of the tournament*/
    public int size = DEFAULT_SIZE;

    /** What's our probability of selection? If 1.0, we always pick the "good" individual. */
    public double probabilityOfSelection;
    
    /** Do we pick the worst instead of the best? */
    public boolean pickWorst;

    public Parameter defaultBase()
        {
        return SelectDefaults.base().push(P_TOURNAMENT);
        }
    
    public void setup(final EvolutionState state, final Parameter base)
        {
        super.setup(state,base);
        
        Parameter def = defaultBase();

        double val = state.parameters.getDouble(base.push(P_SIZE),def.push(P_SIZE),1.0);
        if (val < 1.0)
            state.output.fatal("Tournament size must be >= 1.",base.push(P_SIZE),def.push(P_SIZE));
        else if (val > 1 && val < 2) // pick with probability
            {
            size = 2;
            probabilityOfSelection = (val/2);
            }
        else if (val != (int)val)  // it's not an integer
            state.output.fatal("If >= 2, Tournament size must be an integer.", base.push(P_SIZE), def.push(P_SIZE));
        else
            {
            size = (int)val;
            probabilityOfSelection = 1.0;
            }
        int compareSize = state.parameters.getInt(base.push(P_COMP_SIZE),def.push(P_COMP_SIZE),-1);
        comp_size = compareSize;

        pickWorst = state.parameters.getBoolean(base.push(P_PICKWORST),def.push(P_PICKWORST),false);
        }


    // I hard-code both produce(...) methods for efficiency's sake

    public int produce(final int subpopulation, final EvolutionState state,
			final int thread) {
		// pick size random individuals, then pick the best.
		Individual[] oldinds = state.population.subpops[subpopulation].individuals;
		int i = state.random[thread].nextInt(oldinds.length);
		int bad = i;
		boolean tmpTest = false;

		for (int x = 1; x < size; x++) {
			int j = state.random[thread].nextInt(oldinds.length);
			tmpTest = evaluation(state,
					state.population.subpops[subpopulation], oldinds[j],
					oldinds[i]);
			if (pickWorst) {
//				state.output.message(" produce test (min): " + tmpTest + " "
//						+ j + ", " + i);
				if (!tmpTest) {
					// j (new guy) more desirable than i
					bad = j;
					i = j;
				} else {
					bad = i;
				}
			} else {
//				state.output.message(" produce test (max): " + tmpTest + " "
//						+ j + ", " + i);
				if (tmpTest) {
					// j (new guy) more desirable than i
					bad = j;
					i = j;
				} else {
					bad = i;
				}
			}
		}

		if (probabilityOfSelection < 1.0
				&& !state.random[thread].nextBoolean(probabilityOfSelection))
			i = bad;
		return i;
	}


    // I hard-code both produce(...) methods for efficiency's sake

    /**
      * Produces <i>n</i> individuals from the given subpopulation
        and puts them into inds[start...start+n-1],
        where n = Min(Max(q,min),max), where <i>q</i> is the "typical" number of 
        individuals the BreedingSource produces in one shot, and returns
        <i>n</i>.  max must be >= min, and min must be >= 1. For example, crossover
        might typically produce two individuals, tournament selection might typically
        produce a single individual, etc.
     * @param min
     * @param max
     * @param start
     * @param subpopulation
     * @param inds <strong>RETURNS</strong> selected individuals in inds[start...start+n-1]
     * @param state
     * @param thread
     * @return n - number of individuals returned (must be between min and max)
     * @see ec.SelectionMethod#produce(int, int, int, int, ec.Individual[], ec.EvolutionState, int)
     * @see ec.BreedingSource#produce(int, int, int, int, ec.Individual[], ec.EvolutionState, int)
     */
    public int produce(final int min, 
        final int max, 
        final int start,
        final int subpopulation,
        Individual[] inds,
        final EvolutionState state,
        final int thread) 
        {
        int n = 1;
        if (n>max) n = max;
        if (n<min) n = min;

        for(int q = 0; q < n; q++) {
            // pick size random individuals, then pick the best.
            Individual[] oldinds = state.population.subpops[subpopulation].individuals;
            int i = state.random[thread].nextInt(oldinds.length);
            int bad = i;
            boolean tmpTest = false;
            
            for (int x=1;x<size;x++) {
            	int j = state.random[thread].nextInt(oldinds.length);
            	tmpTest = evaluation(state, state.population.subpops[subpopulation], oldinds[j], oldinds[i]);
            	if (pickWorst) {
//            		state.output.message(" produceN test (min): "+tmpTest+" "+ j +", "+i );
            		if ( !tmpTest ) { 
            			//j (new guy) more desirable than i
            			bad = j; i = j; 
            		} else {
            			bad = i;
            		}
            	}
            	else { 
//            		state.output.message(" produceN test (max): "+tmpTest+ " "+ j +", "+i );
            		if ( tmpTest ) { 
            			//j (new guy) more desirable than i
            			bad = j; i = j;
            		} else {
            			bad = i; 
            		}
            	}
            }            

            if (probabilityOfSelection < 1.0 && !state.random[thread].nextBoolean(probabilityOfSelection))
                i = bad;
            inds[start+q] = oldinds[i];  // note it's a pointer transfer, not a copy!
            }
        return n;
        }

    /**
     * this is an individual trial between teamA and teamB
     * @param state for reference
     * @param teamA the group of individuals representing all subpopulations constituting a full set of players
     * @param teamB the group of individuals representing all subpopulations constituting a full set of players
     * @return true if teamA wins the particular trial
     */
    public boolean trial( EvolutionState state, Subpopulation fromSubPop, Individual[] teamA, Individual[] teamB ) {
    	boolean retVal = false;
    	double valA, valB;
    	CoevoRosenVar2 fxn;
    	fxn = (CoevoRosenVar2)(state.evaluator.p_problem);
    	DoubleVectorIndividual ind1 = (DoubleVectorIndividual) (teamA[0]);
    	DoubleVectorIndividual ind2 = (DoubleVectorIndividual) (teamA[1]);

    	valA = fxn.rosenbrock( ind1.genome[0], ind2.genome[0]);
    	((SimpleFitnessVar2)(ind1.fitness)).improveAltFit(valA);
    	((SimpleFitnessVar2)(ind2.fitness)).improveAltFit(valA);
//    	((SimpleFitnessVar2)(ind1.fitness)).incrementEvalCount();
    	
    	ind1 = (DoubleVectorIndividual) (teamB[0]);
    	ind2 = (DoubleVectorIndividual) (teamB[1]);

    	valB = fxn.rosenbrock( ind1.genome[0], ind2.genome[0]);
    	((SimpleFitnessVar2)(ind1.fitness)).improveAltFit(valB);
    	((SimpleFitnessVar2)(ind2.fitness)).improveAltFit(valB);
//    	((SimpleFitnessVar2)(ind1.fitness)).incrementEvalCount();
    	
//    	state.output.message("\tvalA: "+valA+" valB: "+valB);
    	
    	retVal = valA > valB;
    	SimpleFitnessVar2.incrementEvalCount();
    	return retVal;
    }
    
    /**
     * an evaluation of whether indA is "better" than indB, representing a set of trials, using different team members 
     * from other subpopulations
     * @param state for reference
     * @param indA the individual under trial
     * @param indB the competitor
     * @return true if indA is deemed "better" 
     */
    public boolean evaluation( EvolutionState state, Subpopulation fromSubPop, Individual indA, Individual indB ) {
    	
    	int iWins = 0;
    	boolean tmpWinsA[], tmpWinsB[];
    	boolean retVal = false;
    	Individual[][] seqA, seqB;
    	tmpWinsA = new boolean[comp_size];
    	tmpWinsB = new boolean[comp_size];
    	seqA = seqTeamSelect( state, fromSubPop, indA, comp_size);
    	seqB = seqTeamSelect( state, fromSubPop, indB, comp_size);
    	// for right now, let's call it 3 out of 5
    	for( int trialCt = 0; trialCt < comp_size; trialCt++ ) {
    		boolean locWin = false;
    		Individual[] teamA, teamB;
    		teamA = seqA[trialCt];
    		teamB = seqB[trialCt];
    		locWin = trial(state, fromSubPop, teamA, teamB);
    		if( locWin ) {
    			tmpWinsA[trialCt] = true;
    			tmpWinsB[trialCt] = false;
    		} else {
    			tmpWinsA[trialCt] = false;
    			tmpWinsB[trialCt] = true;
    		}
    	}
    	for( int i = 0; i < comp_size; i++ ) {
			if( ! tmpWinsA[i] ) {
				continue; // already lost, bailing
			}
    		for( int j = 0; j < comp_size; j++ ) {
    			if( ! (tmpWinsA[i] && tmpWinsB[j] ) ) {
    				continue; // already lost, bailing
    			} else { // A and B both winners - fight!
    	    		boolean locWin = false;
    	    		Individual[] teamA, teamB;
    	    		teamA = seqA[i];
    	    		teamB = seqB[j];
    	    		locWin = trial(state, fromSubPop, teamA, teamB);
    	    		if( locWin ) {
    	    			tmpWinsA[i] = true;
    	    			tmpWinsB[j] = false;
    	    		} else {
    	    			tmpWinsA[i] = false;
    	    			tmpWinsB[j] = true;
    	    		}
    				
    			}
    		}
    	}
    	for( int trialCt = 0; trialCt < comp_size; trialCt++ ) {
    		if( tmpWinsA[trialCt] ) {
    			iWins++;
    		}    	
    	}
    	retVal = iWins > 0;
    	return retVal;
    }
    
    /**
     * a routine to assemble a full "team" for a trial
     * @param state for reference - also provides the other subpopulations
     * @param indA the individual from the target subpopulation to act as the 'kernel' of the team - probably currently under evaluation
     * @return
     */
    public Individual[] teamSelect( EvolutionState state, Subpopulation fromSubPop, Individual indA ) {
    	Individual[] retVal;
    	retVal = seqTeamSelect(state, fromSubPop, indA, 1)[0];
//    	retVal = new Individual[ state.population.subpops.length ];
    	return retVal;
    }
    
    /**
     * Generates a sequence of teams of individuals
     * @param state for reference (and subPops)
     * @param fromSubPop indA is from which subPop?
     * @param indA the kernel individual
     * @param seqLen if seqLen <= 0, ALL combinations, else the number of (unique) teams to generate
     * @return a set of teams
     */
    public Individual[][] seqTeamSelect_Internal( EvolutionState state, Subpopulation fromSubPop, Individual indA, int seqLen ) {
    	final int overSelect = 1;
    	Individual[][] retVal;
    	boolean all = false;
    	int internSeqLen = 1;
    	int fromSubPopInd = 0;
    	
    	// figure out the total number of possibles...
    	for( int i = 0; i < state.population.subpops.length; i++ ) {
    		int mult = 1;
    		Subpopulation subpop = null;
    		subpop = state.population.subpops[i];
    		// if we're always going to choose indA from its subpopulation
    		if( subpop == fromSubPop ) {
    			mult = 1;
    			fromSubPopInd = i;
    		} else {
    			// one of the other subpops
    			mult = subpop.individuals.length;
    		}
    		internSeqLen *= mult;
    	}
    	// now that I know how many to select
    	all = (seqLen <= 0 || seqLen > internSeqLen);
    	if( all ) {
    		seqLen = internSeqLen;
    	}
    	retVal = new Individual[seqLen][state.population.subpops.length];

    	// all possible selections
    	int randInd[] = new int[ internSeqLen ];
    	for( int i = 0; i < internSeqLen; i++ ) randInd[i] = 0;
    	// the actually selected indexes
    	int selInd[] = new int[ seqLen ];
    	for( int i = 0; i < seqLen; i++ ) selInd[i] = state.random[0].nextInt(internSeqLen);
    	// sort 'em to make it easier
    	Arrays.sort( selInd );
    	// use a hash-style next-available to remove the duplicates
    	for( int i = 0; i < seqLen; i++ ) {
    		int locInd;
    		locInd = selInd[i];
    		if( randInd[locInd] == 0 ) {
        		// hole is empty
    			randInd[locInd] = 1;
    		} else {
    			// find previous available hole
    			while(randInd[locInd]>0) {
    				locInd -= 1;
    				if( locInd < 0 ) locInd += internSeqLen;
    			}
    			randInd[locInd] += 1;
    		}
    		selInd[i] = locInd;
    	}
    	
    	// now translate the indexes into actual individual selections, populating the returned teams
    	// for each of the team selections
    	for( int i = 0; i < seqLen; i++ ) {
    		int baseInd;
    		baseInd = selInd[i];
    		// for each of the subpopulations
        	for( int j = 0; j < state.population.subpops.length; j++ ) {
        		int sublen;
        		sublen = state.population.subpops[j].individuals.length;
        		if( j == fromSubPopInd ) {
        			retVal[i][j] = indA;
        		} else {
        			int locInd;
        			locInd = baseInd % sublen;
        			baseInd /= sublen;
        			retVal[i][j] = state.population.subpops[j].individuals[locInd];
        		}
        	}    		
    	}

    	return retVal;
    }
    
    public Individual[][] seqTeamSelect( EvolutionState state, Subpopulation fromSubPop, Individual indA, int seqLen ) {
    	final int overSelect = 1;
    	Individual[][] retVal;
    	retVal = new Individual[seqLen][];
    	
//    	retVal = seqTeamSelect_Internal(state, fromSubPop, indA, seqLen);  // TODO baseline implementation to be superseded
    	
    	Individual[][][] internal_hold;
    	double dist[], simFlag, simIntense;
    	simFlag = ((DoubleVectorIndividual)indA).genome[1];
//    	simIntense = ((DoubleVectorIndividual)indA).genome[2];
    	Individual[][] targ;
    	internal_hold = new Individual[overSelect][][];
    	targ = new Individual[overSelect*seqLen][];
    	dist = new double[overSelect*seqLen];
		double subDist[][];
    	subDist = new double[overSelect*seqLen][state.population.subpops.length];

    	for( int i = 0; i < overSelect; i++ ) {
    		internal_hold[i] = seqTeamSelect_Internal(state, fromSubPop, indA, seqLen);
    		for( int j = 0; j < seqLen; j++ ) {
    			int locIndex = i*seqLen + j ;
    			targ[locIndex ] = internal_hold[i][j];
    			for( int k = 0; k < state.population.subpops.length; k++ ) {
    				subDist[locIndex][k] = ((DoubleVectorIndividual)targ[locIndex][k]).genome[1] - simFlag;
    				dist[locIndex] += Math.pow(subDist[locIndex][k],2);
    			}
    			dist[i*overSelect + j] = Math.sqrt( dist[i*overSelect + j] / (state.population.subpops.length - 1));
    		}
    	}
    	double[] sortDist = dist.clone();
    	Arrays.sort(sortDist);
    	double targDist = sortDist[seqLen-1]+Double.MIN_NORMAL;
    	int transfInd = 0;
    	for( int i = 0; i < overSelect; i++ ) {
    		for( int j = 0; j < seqLen; j++ ) {
    			Individual[] locTeam;
    			int locIndex = i*seqLen + j ;
    			locTeam = targ[ locIndex ];
    			if( dist[locIndex] <= targDist ) { // found a good'un
    				retVal[transfInd] = locTeam;
    				transfInd++;
    			}
    			if( transfInd >= seqLen ) break;
    		}
			if( transfInd >= seqLen ) break;
    	}

    	return retVal;
    }
    
    public void individualReplaced(final SteadyStateEvolutionState state,
        final int subpopulation,
        final int thread,
        final int individual)
        { return; }
    
    public void sourcesAreProperForm(final SteadyStateEvolutionState state)
        { return; }
    
	public void bestN( Individual best[], final int N, final int subpopulation, final EvolutionState state) {
		Individual retVal[] = new Individual[ N ];
		Individual sourcePool[];
		boolean used[];
		sourcePool = state.population.subpops[subpopulation].individuals;
		used = new boolean[sourcePool.length];
		int winB, winE;
		
		// set the initial contestents
		winB = 0; winE = winB+N;
		for( int i = winB; i < winE; i++ ) {
			retVal[i] = sourcePool[i];
			used[i] = true;
		}
		
		winB = N; winE = winB+N; winE = winE<=sourcePool.length?winE:sourcePool.length;
		// now compare the return set against each window
		while( winB < sourcePool.length ) {
			// for each of the best-to-date values
			for( int i = 0; i < N; i++ ) {
				// compare to each of the window values, replacing "best" if needed
				for( int j = 0; (j < N) && (winB+j < winE ); j++ ) {
					if( used[winB+j]) continue; // if the challenger has already been promoted...
					Individual indA = retVal[i];
					Individual indB = sourcePool[winB+j];
					boolean locWin = false;
					// so who wins?
					locWin = evaluation(state, state.population.subpops[subpopulation], indA, indB);
					// if not the favorite, then challenger is the new favorite, and continues to drive on.
					// drat - need a flag to keep a super-indiv from occupying all the return slots - wouldn't actively be a problem if 
					// swapping, but since i'm leaving the original 'from' intact, i need to provide a flag
					if( ! locWin ) {
						retVal[i] = sourcePool[winB+j];
						used[winB+j] = true;
					}
				}
			}
			// next window....
			winB += N; winE = winB+N; winE = winE<=sourcePool.length?winE:sourcePool.length;
		}
		for( int i = 0; i < N; i++ ) {
			best[i] = retVal[i];
		}
		
		return;
	}
	
    }
